package algotithm.leetcode.dp.test1230;

/**
 * @author 25068
 * @Date 2021/5/4 10:52
 * @Title 1230. 抛掷硬币
 */
public class Solution {

    public static void main(String[] args) {
        double[] prob = {0.5,0.5,0.5,0.5,0.5};
        int target = 0;
        Solution solution = new Solution();
        double res = solution.probabilityOfHeads(prob, target);
        System.out.println(res);
    }

    public double probabilityOfHeads(double[] prob, int target) {
        int n = prob.length;
        // dp[i][j] 表示前 i 个硬币中，j 个硬币朝上的概率
        double[][] dp = new double[n + 1][target + 1];
        // “一个硬币都没有，一个朝上的都没” 是确定事件，因此概率为 1
        dp[0][0] = 1.0;
        for (int i = 1; i <= n; i++) {
            // 给定的硬币全朝下
            dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i-1][j] * (1 - prob[i-1]) + dp[i-1][j-1] * prob[i-1];
            }
        }
        return dp[n][target];
    }
}


